In virtually every modem transmission or reception device, such as those for, e.g., GSM and UMTS R99, a data interleaving step, i.e. a data reordering step, is used.
Data interleaving is the process of reordering the data according to some predetermined pattern. Typically, the interleaving uses a block interleaving pattern, wherein the data is organized in a rectangular matrix. First the whole interleaving block is written to the memory according to a well-chosen access sequence, and then the block is read out by means of the second access sequence. For example, the matrix is written in the order of the rows but read in the order of the columns. These sequences combined implement the required interleaving operation.
Note that by using an interleaving scheme's access sequences, while swapping the reading and writing commands, its associated deinterleaving scheme is obtained. For example, the matrix is written in the order of the columns but read in the order of the rows. A data interleaver and corresponding deinterleaver are typically implemented as write and read sequences to a Random access memory (RAM).
Interleaving has an inherent high latency associated with its operation because of its data dependencies.
Interleaving has numerous applications in the area of computer science, error correcting codes and communications. For example, if data is interleaved prior to encoding with an error correcting code the data becomes less vulnerable to burst errors. The latter is especially important for communications, including mobile communications, but is also used for data storage. Data interleaving can also be used for multiplexing multiple sources of digital streams, for example, to combine a digital audio stream and a digital video stream into one multimedia stream.
If the required data-rates are low, often programmable solutions on a DSP or micro-controller are used. For higher data-rates and/or throughput requirements a random access memory with dedicated address generation hardware is used, for example, for WLAN.
The throughput requirements on a memory used for interleaving have been constantly rising. The most important reason for this is the increasing data rates required by the communication standards. To give an indication of this increase, the throughput requirements for 3 G communication standards are given below in Table 1 below, along with a next generation in the Table 2 below. Note: Msbit/s stands for Mega soft-bits per second, which is a measurement of data rate. One soft-bit corresponds with 4 or 5 real bits, depending on the precision used by the demodulator.
TABLE 13G StandardsStandardThroughput802.11a/g72 Msbit/sDAB4.6 Msbit/s DVB81 Msbit/sUMTS8.8 Msbit/s HSDPA42 Msbit/s
TABLE 24G StandardsStandardThroughputUMTS LTE300 Msbit/s802.11n600 Msbit/s
Furthermore, upstream and downstream activities often have to be supported simultaneously, leading to a higher architecture load. Also, multi-standard solutions not only have to process the sum of the individual data rates, but can be stressed even further because of tight latency constraints. The result of these developments is that the sum of access rates on the memory has become much larger than the maximally attainable memory frequency.
If a multi-bank memory is used, a new problem arises: if two or more elements of an access vector are assigned to the same bank a so-called conflict occurs since a single bank can only process one element at a time. For example, such a conflict occurs if an access vector, i.e. a command vector, contains two write commands destined for the same memory bank. The distributor can resolve this conflict by splitting the access vector up into two new access vectors such that each new access vector comprises only one of the two addresses that gave rise to the conflict. As a result, two cycles are used to process the original access vector. This corresponds with a memory efficiency of 50%.
Depending on the characteristics of the interleaving scheme, it is seldom possible to process many consecutive access vectors without having bank conflicts.
The worst-case scenario for bank conflicts occurs for certain block interleaving access patterns. If the number of banks, P, is a divider of the number of columns, C, of the matrix, i.e. the block interleaving function, a total of C bursts of bank conflicts occur. In this case the memory efficiency drops to only 1/P*100%. In particular, this situation occurs in the situation where the number of columns is equal to the number of banks used.
It is a problem of known memory architectures that they are inefficient if used for data interleaving.